#include <bits/stdc++.h>
// 2025/04/02
// tag: 
// Author: Forever
using namespace std;
const int maxn = 30001;
int n, m, s, t;
bool v[maxn];
bitset<maxn> vis[maxn];
vector<int> G[maxn];
queue<pair<int, int>> q;

void insert(int i, int p){
    if (i < 0 || i >= n)
        return;
    if (!v[i]){
        v[i] = true;
        for (int x : G[i])
            if (!vis[i][x])
                vis[i][x] = true, q.push({i, x});
    }
    if (!vis[i][p])
        vis[i][p] = true, q.push({i, p});
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    int B, P, p;
    cin >> s >> P;
    G[s].push_back(P);
    cin >> t >> p;
    G[t].push_back(p);
    for (int i = 3; i <= m; i++) {
        cin >> B >> p;
        G[B].push_back(p);
    }
    int cnt = 0;
    insert(s, P);
    while (!q.empty()){
        int l = q.size();
        for (int i = 1; i <= l; i++) {
            auto [id, p] = q.front();
            q.pop();
            if (id == t)
                return cout << cnt << endl, 0;
            insert(id - p, p);
            insert(id + p, p);
        }
        cnt++;
    }
    cout << -1 << endl;
    return 0;
}